public class Test2 {
    //leetcode 377 组合总和II
    public int combinationSum4(int[] nums, int target) {
        //动态规划问题，解决的是数组的组合问题，而这道问题解决的是数组的排列的问题，那么这就意味着
        //这道题目不能使用动态规划来解决了吗？不是的，虽然我们的动态规划解决的是数组的组合问题，但是
        //动态规划的初心是为了将之前计算的结果给存储在数组中，避免重复计算，所以这里我们抽象出来
        //一个状态表示：dp[i]表示总和为i的时候一共有多少种排列方式
        //状态转移方程，根据最后一个位置划分，最后一个位置可以选择数组的任意一个元素
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (int x : nums) {
                if (x <= i) {
                    dp[i] += dp[i - x];
                }
            }
        }
        return dp[target];
    }
}
